/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var movingCount = function(m, n, k) {
  let result = new Map(), count = 0;
  function isValidMove(i, j) {
    if(i >= m || j >= n) return false;
    if(i % 10 + Math.floor(i / 10) + j % 10 + Math.floor(j / 10) <= k) {
      return true;
    } else {
      return false;
    }
  }
  function dfs(i, j) {
    if(!isValidMove(i, j)) return ;
    if(result.has(i)) {
      if(result.get(i).indexOf(j) == -1) {
        result.get(i).push(j);
        count++;
      } else {
        return;
      }
    } else {
      result.set(i, [j]);
      count++;
    }
    dfs(i + 1, j);
    dfs(i, j + 1);
  }
  dfs(0, 0);
  return count;
};
let m = 2, n = 3, k = 1;
console.log(movingCount(m, n, k));
m = 3, n = 1, k = 0;
console.log(movingCount(m, n, k));
m = 1, n = 2, k = 1;
console.log(movingCount(m, n, k));
m = 3, n = 2, k = 17;
console.log(movingCount(m, n, k));
